package unionFindStudy;

import common.utils.UnionFind;

import java.util.*;

public class UnionFindStudy02 {

    /**
     * 给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。
     *
     * 现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。
     *
     * 合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是按字符 ASCII 顺序排列的邮箱地址。账户本身可以以任意顺序返回。
     * @param args
     */
    public static void main(String[] args) {

    }

    public static List<List<String>> accountsMerge(List<List<String>> accounts){
        //记录邮箱和邮箱的id
        Map<String, Integer> emailToId = new HashMap<>();
        //id的个数
        int n = accounts.size();
        UnionFind unionFind = new UnionFind(n);
        for (int i = 0; i < n; i++){
            List<String> account = accounts.get(i);
            int m = account.size();
            for (int j = 1; j < m; j++){
                String email = account.get(j);
                if (emailToId.containsKey(email)){
                    //如果前面有账户含有这个邮箱，那么合并前面的账户和当前账户
                    unionFind.union(emailToId.get(email), i);
                } else {
                    //将该邮箱放进map中
                    emailToId.put(email, i);
                }
            }
        }

        //存放idToEmail
        Map<Integer, List<String>> idToEmail = new HashMap<>();
        //将emailToId转化为idToEmail
        for (Map.Entry<String, Integer> entry : emailToId.entrySet()) {
            //得到索引
            int id_root = unionFind.find(entry.getValue());
            List<String> emails = idToEmail.getOrDefault(id_root, new ArrayList<>());
            emails.add(entry.getKey());
            idToEmail.put(id_root, emails);
        }
        //将元素合并
        List<List<String>> ans = new LinkedList<>();
        for (Integer key : idToEmail.keySet()) {
            List<String> emails = idToEmail.get(key);
            Collections.sort(emails);
            LinkedList<String> account = new LinkedList<>(emails);
            account.addFirst(accounts.get(key).get(0));
            ans.add(account);
        }
        return ans;
    }
}
